#include <algorithm>
#include <cmath>
#include <functional>
#include <iostream>
#include <vector>
/*
桶排序算法实现
*/
void bucket_sort(std::vector<int> &v, int min, int max) {
  // 计算桶的数量 每个桶中元素数量为2
  float k = (max - min) / 2.0;
  int bucket_num = std::ceil(k);
  // 计算每个桶中容纳元素的跨度
  int space = (max - min) / bucket_num;
  std::vector<std::vector<int>> buckets(bucket_num);
  // 将元素依次放入对应的桶中
  for (const int &item : v) {
    int index = (item - min) / space;
    buckets[index].push_back(item);
  }
  // 对各个桶中元素进行排序
  for (std::vector<int> bucket : buckets) {
    std::sort(bucket.begin(), bucket.end(), std::greater<int>());
  }
  // 合并各个桶中的元素
  int n = 0;
  for (std::vector<int> bucket : buckets) {
    for (int i : bucket) {
      v[n++] = bucket[n % bucket.size()];
    }
  }
}

int main() {
  std::vector<int> list = {9, 8, 6, 4, 5, 3, 1, 2};
  bucket_sort(list, 0, 10);
  for (int &i : list) {
    std::cout << i;
  }

  return 0;
}